package com.springboot.study.tests.sort;

import java.io.IOException;

/**
 * @Author: guodong
 * @Date: 2021/5/17 10:08
 * @Version: 1.0
 * @Description:
 */
public class MaxHeap {

    public static void main(String args[]) throws IOException{

        int i,size,data[]={0,5,6,10,8,3,2,19,9,11}; //原始数组内容

        size=data.length;

        System.out.print("原始数组：");

        for(i=1;i<size;i++)
            System.out.print("["+data[i]+"] ");

        System.out.println("");

        MaxHeap.heap(data,size);            //建立堆积树
    }

    public static void heap(int data[] ,int size){
        int i,j,tmp;
        for(i=(size/2);i>0;i--)             //建立堆积树节点
            MaxHeap.ad_heap(data,i,size-1);
        System.out.print("\n堆积内容：");
        for(i=1;i<size;i++)             //原始堆积树内容
            System.out.print("["+data[i]+"] ");
    }

    public static void ad_heap(int data[],int i,int size){
        int j,tmp,post;
        j=2*i;
        tmp=data[i];
        post=0;
        while(j<=size && post==0){
            if(j<size)
            {
                //if(data[j]>data[j+1]) //小顶堆的比较
                if(data[j]<data[j+1])   //找出两个子节点最大值
                    j++;
            }
            //if(tmp<=data[j])          //小顶堆的比较
            if(tmp>=data[j])            //若树根较大，结束比较过程
                post=1;
            else
            {
                data[j/2]=data[j];      //若树根较小，则继续比较，这里将最大子节点赋值给父节点
                j=2*j;
            }
        }
        data[j/2]=tmp;                   //指定树根为父节点
    }
}